// 给定非负整数数组，数组元素代表该位置可以前进的最大长度，判断能否到达最后一个位置
/**
 * example1:[2,3,1,1,4]
 * 从起始位置开始先走1步，再走3步可以到达末尾
 * return true
 * example2:[3,2,1,0,4]
 * return false
 */
// 解法1 top to bottom
var canJump1 = function (nums) {
    // 建立表格，0表示未知，1表示通，-1表示不通
    const totalLength = nums.length
    // 初始全部为0表示未知
    const memo = Array(totalLength).fill(0)
    // 终点记为1表示通
    memo[totalLength - 1] = 1

    function jump(position) {
        // 结束条件
        if (memo[position] === 1) {
            return true
        } else if (memo[position] === -1) {
            return false
        }

        // 记录从当前位置position能走的最远距离 并防止数组越界
        const maxJump = Math.min(position + nums[position], totalLength - 1)

        // 循环从当前点能走的所有分支
        for (let i = position + 1; i <= maxJump; i++) {
            const jumpResult = jump(i)
            if (jumpResult === true) {
                memo[position] = 1
                return true
            }
        }

        // 没有能走通的记为-1
        memo[position] = -1
        return false
    }

    // 从起始位置开始走
    return jump(0)
}

// 解法2 bottom to top
var canJump2 = function (nums) {
    // 建立表格，0表示未知，1表示通，-1表示不通
    const totalLength = nums.length
    // 初始全部为0表示未知
    const memo = Array(totalLength).fill(0)
    // 终点记为1表示通
    memo[totalLength - 1] = 1

    // 从终点往前看
    for (let i = totalLength - 2; i >= 0; i--) {
        // 记录从当前位置能走的最远距离 并防止数组越界
        const maxJump = Math.min(i + nums[i], totalLength - 1)
        // 从当前位置往后走，看是否存在memo[j]为1的点
        for (let j = i + 1; j < maxJump; j++) {
            if (memo[j] === 1) {
                memo[i] = 1
                break
            }
        }
    }

    // 如果前面的for循环走到了最开始，则memo[0] = 1
    if (memo[0] === 1) {
        return true
    } else {
        return false
    }
}

// 解法3 贪心算法
var canJump3 = function (nums) {
    // 初始位置在终点
    let maxJump = nums.length - 1
    // 从后往前看
    for (let i = nums.length - 2; i >= 0; i--) {
        // 如果从i能走到maxJump就是通的，并把maxJump更新为当前点
        // 因为能走到当前点就一定能走到终点
        if (i + nums[i] >= maxJump) {
            maxJump = i
        }
    }
    // maxJump能回到起始点则返回true
    return maxJump === 0
}
